package java_thinking.unit_17._17_9_10;

import java_thinking.unit_17._17_2_6.Countries;

import java.util.*;

/**
 * @Desc:   简单的实现散列功能
 * @author: cww
 * @DateTime: 2019/4/19 19:00
 */

public class SimpleHashMap<K,V> extends AbstractMap<K,V> {

    /**
     * 事实证明，质数实际上并不是散列桶的理想容量，近来，经过广泛的测试，java的散列函数都使用2的
     * 整数次方，对于现代的处理器来说，除法与求余数是最慢的操作，使用2的整数次方长度的散列表，可用
     * 掩码代替除法，因为get()是使用最多的操作，求余数的%操作是其开销最大的部分，而是用2的整数次方
     * 可以消除此开销(也可能对hashCode()有些影响)
     */
    static final int SIZE = 997;

    @SuppressWarnings("unchecked")
    LinkedList<SlowMap.MapEntry<K,V>>[] buckets = new LinkedList[SIZE];

    @Override
    public V put(K key, V value) {
        V oldValue = null;
        //计算出key的散列码
        int index = Math.abs(key.hashCode()) % SIZE;
        SlowMap.MapEntry<K,V> tmpPair = new SlowMap.MapEntry<K,V>(key, value);
        //查询桶里面是否有以该散列码的键值对，如果没有新建一个list对象放在桶里该位置，该list用于存put进来的放键值对
        if (buckets[index] == null) {
            buckets[index] = new LinkedList<SlowMap.MapEntry<K,V>>();
        } else {
            //这里是练习20 让该map能够报告冲突
            System.out.println("Collision while adding\n" + tmpPair + "\nBucket already contains:");
            Iterator<SlowMap.MapEntry<K,V>> it = buckets[index].iterator();
            while(it.hasNext())
                System.out.println(it.next());
        }
        LinkedList<SlowMap.MapEntry<K,V>> bucket = buckets[index];
        //将put传入参数包装成Map
        SlowMap.MapEntry<K,V> pair = new SlowMap.MapEntry<K,V>(key,value);
        boolean found = false;
        //遍历桶里该位置的list，list中是否存在与当前传入的key相同的map对象，
        //如果存在则替换该map对象的Value，返回oldValue
        ListIterator<SlowMap.MapEntry<K,V>> it = bucket.listIterator();
        while (it.hasNext()) {
            SlowMap.MapEntry<K,V> iPair = it.next();
            if (iPair.getKey().equals(key)) {
                oldValue = iPair.getValue();
                it.set(pair);
                found = true;
                break;
            }
        }
        //如果list不存在当前插入的map对象同key值，则将插入的map存入list末端
        if (!found) {
            buckets[index].add(pair);
        }
        return oldValue;
    }

    @Override
    public V get(Object key) {
        int index = Math.abs(key.hashCode()) % SIZE;
        if (buckets[index] == null) {
            return null;
        }
        for (SlowMap.MapEntry<K,V> mapEntry : buckets[index]) {
            if (mapEntry.getKey().equals(key)) {
                return mapEntry.getValue();
            }
        }
        return null;
    }

    @Override
    public Set<Map.Entry<K, V>> entrySet() {
        Set<Map.Entry<K, V>> set = new LinkedHashSet<>();
        for (LinkedList<SlowMap.MapEntry<K,V>> bucket : buckets) {
            if (bucket == null) {
                continue;
            }
            for (SlowMap.MapEntry<K,V> mapEntry : bucket) {
                set.add(mapEntry);
            }
        }
        return set;
    }

    public static void main(String[] args) {
        SimpleHashMap<String,String> map = new SimpleHashMap<>();
        map.putAll(Countries.capitals(10));
        System.out.println(map);
        map.put("CAPE VERDE","beijing");
        System.out.println(map.get("CENTRAL AFRICAN REPUBLIC"));
        System.out.println(map.get("CAPE VERDE"));
        System.out.println(map.entrySet());
    }
}
